// SPDX-License-Identifier: Apache-2.0

package chisel3

import chisel3.experimental.VecLiterals.AddVecLiteralConstructor
import chisel3.experimental.dataview.{isView, reifySingleData, InvalidViewException}

import scala.collection.immutable.{SeqMap, VectorMap}
import scala.collection.mutable.{HashSet, LinkedHashMap}
import scala.language.experimental.macros
import chisel3.experimental.{BaseModule, BundleLiteralException, HasTypeAlias, OpaqueType, VecLiteralException}
import chisel3.experimental.{SourceInfo, UnlocatableSourceInfo}
import chisel3.internal._
import chisel3.internal.Builder.pushCommand
import chisel3.internal.firrtl._
import chisel3.internal.sourceinfo.{SourceInfoTransform, VecTransform}
import chisel3.reflect.DataMirror
import _root_.firrtl.{ir => fir}

import java.lang.Math.{floor, log10, pow}
import scala.collection.mutable

class AliasedAggregateFieldException(message: String) extends chisel3.ChiselException(message)

sealed abstract class Aggregate extends Data {

  private def checkingLitOption(checkForDontCares: Boolean): Option[BigInt] = {
    def shiftAdd(accumulator: Option[BigInt], elt: Data): Option[BigInt] = {
      (accumulator, elt.litOption) match {
        case (Some(accumulator), Some(eltLit)) =>
          val width = elt.width.get
          val masked = ((BigInt(1) << width) - 1) & eltLit // also handles the negative case with two's complement
          Some((accumulator << width) + masked)
        case (Some(accumulator), None) if checkForDontCares =>
          Builder.error(s"Called litValue on aggregate $this contains DontCare")(UnlocatableSourceInfo)
          None
        case (None, _) => None
        case (_, None) => None
      }
    }

    topBindingOpt match {
      case Some(BundleLitBinding(_)) | Some(VecLitBinding(_)) =>
        getElements.reverse
          .foldLeft[Option[BigInt]](Some(BigInt(0)))(shiftAdd)
      case _ => None
    }
  }

  override def litOption: Option[BigInt] = {
    checkingLitOption(checkForDontCares = false)
  }

  override def litValue: BigInt = {
    checkingLitOption(checkForDontCares = true).get
  }

  def getElements: Seq[Data]

  private[chisel3] def elementsIterator: Iterator[Data]

  private[chisel3] def width: Width = elementsIterator.map(_.width).foldLeft(0.W)(_ + _)

  private[chisel3] def firrtlConnect(that: Data)(implicit sourceInfo: SourceInfo): Unit = {
    if (that == DontCare) {
      pushCommand(DefInvalid(sourceInfo, lref))
    } else {
      pushCommand(Connect(sourceInfo, lref, Node(that)))
    }
  }

  override private[chisel3] def _asUIntImpl(first: Boolean)(implicit sourceInfo: SourceInfo): UInt = {
    val elts = this.getElements.map(_._asUIntImpl(false))
    if (elts.isEmpty && !first) 0.U(0.W) else SeqUtils.do_asUInt(elts)
  }

  private[chisel3] override def connectFromBits(
    that: Bits
  )(
    implicit sourceInfo: SourceInfo
  ): Unit = {
    var i = 0
    val bits = if (that.isLit) that else WireDefault(UInt(this.width), that) // handles width padding
    for (x <- flatten) {
      val fieldWidth = x.getWidth
      if (fieldWidth > 0) {
        x.connectFromBits(bits(i + fieldWidth - 1, i))
        i += fieldWidth
      } else {
        x := DontCare
      }
    }
  }
}

trait VecFactory extends SourceInfoDoc {

  def apply[T <: Data](n: Int, gen: T)(implicit sourceInfo: SourceInfo): Vec[T] = {
    requireIsChiselType(gen, "vec type")
    new Vec(gen.cloneTypeFull, n)
  }

  private[chisel3] def truncateIndex(
    idx: UInt,
    n:   BigInt
  )(
    implicit sourceInfo: SourceInfo
  ): UInt = {
    val w = (n - 1).bitLength
    if (n <= 1) 0.U
    else if (idx.width.known && idx.width.get <= w) idx
    else if (idx.width.known) idx(w - 1, 0)
    else (idx | 0.U(w.W))(w - 1, 0)
  }
}


sealed class Vec[T <: Data] private[chisel3] (gen: => T, val length: Int) extends Aggregate with VecLike[T] {

  override def toString: String = {
    topBindingOpt match {
      case Some(VecLitBinding(vecLitBinding)) =>
        val contents = vecLitBinding.zipWithIndex.map {
          case ((data, lit), index) =>
            s"$index=$lit"
        }.mkString(", ")
        s"${sample_element.cloneType}[$length]($contents)"
      case _ => stringAccessor(s"${sample_element.cloneType}[$length]")
    }
  }

  override def typeName = s"Vec${length}_${gen.typeName}"

  override def containsAFlipped = sample_element.containsAFlipped

  private[chisel3] override def bind(target: Binding, parentDirection: SpecifiedDirection): Unit = {
    this.maybeAddToParentIds(target)
    binding = target

    val resolvedDirection = SpecifiedDirection.fromParent(parentDirection, specifiedDirection)
    sample_element.bind(SampleElementBinding(this), resolvedDirection)
    for (child <- elementsIterator) { // assume that all children are the same
      child.bind(ChildBinding(this), resolvedDirection)
    }

    direction =
      ActualDirection.fromChildren(Set(sample_element.direction), resolvedDirection).getOrElse(ActualDirection.Empty)
  }

  private lazy val self: Seq[T] = {
    val _self = Vector.fill(length)(gen)
    for ((elt, i) <- _self.zipWithIndex)
      elt.setRef(this, i)
    _self
  }

  private[chisel3] val sample_element: T = gen

  private[chisel3] final override def allElements: Seq[Element] =
    (sample_element +: self).flatMap(_.allElements)

  def <>(that: Seq[T])(implicit sourceInfo: SourceInfo): Unit = {
    if (this.length != that.length)
      Builder.error(
        s"Vec (size ${this.length}) and Seq (size ${that.length}) being bulk connected have different lengths!"
      )
    for ((a, b) <- this.zip(that)) {
      a <> b
    }
  }

  def <>(that: Vec[T])(implicit sourceInfo: SourceInfo): Unit =
    this.bulkConnect(that.asInstanceOf[Data])

  def :=(that: Seq[T])(implicit sourceInfo: SourceInfo): Unit = {
    require(
      this.length == that.length,
      s"Cannot assign to a Vec of length ${this.length} from a Seq of different length ${that.length}"
    )
    for ((a, b) <- this.zip(that))
      a := b
  }

  def :=(that: Vec[T])(implicit sourceInfo: SourceInfo): Unit = this.connect(that)

  override def do_apply(p: UInt)(implicit sourceInfo: SourceInfo): T = {
    requireIsHardware(this, "vec")
    requireIsHardware(p, "vec index")

    p.litOption match {
      case Some(idx) if idx < length => return this.apply(idx.intValue)
      case _                         => // Fall through to control flow below
    }

    if (length == 0) {
      Builder.warning(Warning(WarningID.ExtractFromVecSizeZero, s"Cannot extra from Vec of size 0."))
    } else {
      p.widthOption.foreach { pWidth =>
        val correctWidth = BigInt(length - 1).bitLength
        def mkMsg(msg: String): String =
          s"Dynamic index with width $pWidth is too $msg for Vec of size $length (expected index width $correctWidth)."

        if (pWidth > correctWidth) {
          Builder.warning(Warning(WarningID.DynamicIndexTooWide, mkMsg("wide")))
        } else if (pWidth < correctWidth) {
          Builder.warning(Warning(WarningID.DynamicIndexTooNarrow, mkMsg("narrow")))
        }
      }
    }

    if (isView(this)) {
      reifySingleData(this) match {
        case Some(target: Vec[T @unchecked])
            if this.length == target.length &&
              this.sample_element.typeEquivalent(target.sample_element) =>
          return target.apply(p)
        case _ => throw InvalidViewException("Dynamic indexing of Views is not yet supported")
      }
    }

    val port = gen

    val reconstructedResolvedDirection = direction match {
      case ActualDirection.Input  => SpecifiedDirection.Input
      case ActualDirection.Output => SpecifiedDirection.Output
      case ActualDirection.Bidirectional(ActualDirection.Default) | ActualDirection.Unspecified =>
        SpecifiedDirection.Unspecified
      case ActualDirection.Bidirectional(ActualDirection.Flipped) => SpecifiedDirection.Flip
      case ActualDirection.Empty                                  => SpecifiedDirection.Unspecified
    }
    port.bind(ChildBinding(this), reconstructedResolvedDirection)

    val i = Vec.truncateIndex(p, length)(UnlocatableSourceInfo)
    port.setRef(this, i)

    port
  }

  def apply(idx: Int): T = self(idx)

  override def cloneType: this.type = {
    new Vec(gen.cloneTypeFull, length).asInstanceOf[this.type]
  }

  override def getElements: Seq[Data] = self

  final override private[chisel3] def elementsIterator: Iterator[Data] = self.iterator

  def toPrintable: Printable = {
    val elts =
      if (length == 0) List.empty[Printable]
      else self.flatMap(e => List(e.toPrintable, PString(", "))).dropRight(1)
    PString("Vec(") + Printables(elts) + PString(")")
  }

  def reduceTree(redOp: (T, T) => T): T = macro VecTransform.reduceTreeDefault

  def reduceTree(redOp: (T, T) => T, layerOp: (T) => T): T = macro VecTransform.reduceTree

  def do_reduceTree(
    redOp:   (T, T) => T,
    layerOp: (T) => T = (x: T) => x
  )(
    implicit sourceInfo: SourceInfo
  ): T = {
    require(!isEmpty, "Cannot apply reduction on a vec of size 0")

    def recReduce[T](s: Seq[T], op: (T, T) => T, lop: (T) => T): T = {

      val n = s.length
      n match {
        case 1 => lop(s(0))
        case 2 => op(s(0), s(1))
        case _ =>
          val m = pow(2, floor(log10(n - 1) / log10(2))).toInt // number of nodes in next level, will be a power of 2
          val p = 2 * m - n // number of nodes promoted

          val l = s.take(p).map(lop)
          val r = s
            .drop(p)
            .grouped(2)
            .map {
              case Seq(a, b) => op(a, b)
            }
            .toVector
          recReduce(l ++ r, op, lop)
      }
    }

    recReduce(this, redOp, layerOp)
  }

  private[chisel3] def _makeLit(
    elementInitializers: (Int, T)*
  )(
    implicit sourceInfo: SourceInfo
  ): this.type = {

    def checkLiteralConstruction(): Unit = {
      val dupKeys = elementInitializers.map { x => x._1 }.groupBy(x => x).flatMap {
        case (k, v) =>
          if (v.length > 1) {
            Some(k, v.length)
          } else {
            None
          }
      }
      if (dupKeys.nonEmpty) {
        throw new VecLiteralException(
          s"VecLiteral: has duplicated indices ${dupKeys.map { case (k, n) => s"$k($n times)" }.mkString(",")}"
        )
      }

      val outOfRangeIndices = elementInitializers.map(_._1).filter { case index => index < 0 || index >= length }
      if (outOfRangeIndices.nonEmpty) {
        throw new VecLiteralException(
          s"VecLiteral: The following indices (${outOfRangeIndices.mkString(",")}) " +
            s"are less than zero or greater or equal to than Vec length"
        )
      }
      cloneSupertype(elementInitializers.map(_._2), s"Vec.Lit(...)")

      val badLits = elementInitializers.flatMap {
        case (index, lit) =>
          (sample_element.width, lit.width) match {
            case (KnownWidth(m), KnownWidth(n)) =>
              if (m < n) Some(index -> lit) else None
            case (KnownWidth(_), _) =>
              None
            case (UnknownWidth(), _) =>
              None
            case _ =>
              Some(index -> lit)
          }
        case _ => None
      }
      if (badLits.nonEmpty) {
        throw new VecLiteralException(
          s"VecLiteral: Vec[$gen] has the following incorrectly typed or sized initializers: " +
            badLits.map { case (a, b) => s"$a -> $b" }.mkString(",")
        )
      }

    }

    requireIsChiselType(this, "vec literal constructor model")
    checkLiteralConstruction()

    val clone = cloneType
    val cloneFields = getRecursiveFields(clone, "(vec root)").toMap

    val vecLitLinkedMap = new mutable.LinkedHashMap[Data, LitArg]()
    elementInitializers.sortBy { case (a, _) => a }.foreach {
      case (fieldIndex, value) =>
        val field = clone.apply(fieldIndex)
        val fieldName = cloneFields.getOrElse(
          field,
          throw new VecLiteralException(
            s"field $field (with value $value) is not a field," +
              s" ensure the field is specified as a function returning a field on an object of class ${this.getClass}," +
              s" eg '_.a' to select hypothetical bundle field 'a'"
          )
        )

        val valueBinding = value.topBindingOpt match {
          case Some(litBinding: LitBinding) => litBinding
          case _ => throw new VecLiteralException(s"field $fieldIndex specified with non-literal value $value")
        }

        field match { // Get the litArg(s) for this field
          case bitField: Bits =>
            if (!field.typeEquivalent(bitField)) {
              throw new VecLiteralException(
                s"VecLit: Literal specified at index $fieldIndex ($value) does not match Vec type $sample_element"
              )
            }
            if (bitField.getWidth > field.getWidth) {
              throw new VecLiteralException(
                s"VecLit: Literal specified at index $fieldIndex ($value) is too wide for Vec type $sample_element"
              )
            }
            val litArg = valueBinding match {
              case ElementLitBinding(litArg) => litArg
              case BundleLitBinding(litMap) =>
                litMap.getOrElse(
                  value,
                  throw new BundleLiteralException(s"Field $fieldName specified with unspecified value")
                )
              case VecLitBinding(litMap) =>
                litMap.getOrElse(
                  value,
                  throw new VecLiteralException(s"Field $fieldIndex specified with unspecified value")
                )
            }
            val adjustedLitArg = litArg.cloneWithWidth(sample_element.width)
            vecLitLinkedMap(bitField) = adjustedLitArg

          case recordField: Record =>
            if (!(recordField.typeEquivalent(value))) {
              throw new VecLiteralException(
                s"field $fieldIndex $recordField specified with non-type-equivalent value $value"
              )
            }
            val remap = getMatchedFields(value, recordField).toMap
            valueBinding.asInstanceOf[BundleLitBinding].litMap.map {
              case (valueField, valueValue) =>
                vecLitLinkedMap(remap(valueField)) = valueValue
            }

          case vecField: Vec[_] =>
            if (!(vecField.typeEquivalent(value))) {
              throw new VecLiteralException(
                s"field $fieldIndex $vecField specified with non-type-equivalent value $value"
              )
            }
            val remap = getMatchedFields(value, vecField).toMap
            value.topBinding.asInstanceOf[VecLitBinding].litMap.map {
              case (valueField, valueValue) =>
                vecLitLinkedMap(remap(valueField)) = valueValue
            }

          case enumField: EnumType => {
            if (!(enumField.typeEquivalent(value))) {
              throw new VecLiteralException(
                s"field $fieldIndex $enumField specified with non-type-equivalent enum value $value"
              )
            }
            val litArg = valueBinding match {
              case ElementLitBinding(litArg) => litArg
              case _ =>
                throw new VecLiteralException(s"field $fieldIndex $enumField could not bematched with $valueBinding")
            }
            vecLitLinkedMap(field) = litArg
          }

          case _ => throw new VecLiteralException(s"unsupported field $fieldIndex of type $field")
        }
    }

    clone.bind(VecLitBinding(VectorMap(vecLitLinkedMap.toSeq: _*)))
    clone
  }
}

object VecInit extends SourceInfoDoc {

  private def getConnectOpFromDirectionality[T <: Data](
    proto: T
  )(
    implicit sourceInfo: SourceInfo
  ): (T, T) => Unit = proto.direction match {
    case ActualDirection.Input | ActualDirection.Output | ActualDirection.Unspecified =>
      (x, y) => x := y
    case ActualDirection.Bidirectional(_) =>
      (x, y) => x <> y
    case ActualDirection.Empty =>
      (x, y) => x <> y
  }

  def apply[T <: Data](elts: Seq[T]): Vec[T] = macro VecTransform.apply_elts

  def do_apply[T <: Data](elts: Seq[T])(implicit sourceInfo: SourceInfo): Vec[T] = {
    require(elts.nonEmpty, "Vec hardware values are not allowed to be empty")
    elts.foreach(requireIsHardware(_, "vec element"))

    val vec = Wire(Vec(elts.length, cloneSupertype(elts, "Vec")))
    val op = getConnectOpFromDirectionality(vec.head)

    (vec.zip(elts)).foreach { x =>
      op(x._1, x._2)
    }
    vec
  }

  def apply[T <: Data](elt0: T, elts: T*): Vec[T] = macro VecTransform.apply_elt0

  def do_apply[T <: Data](elt0: T, elts: T*)(implicit sourceInfo: SourceInfo): Vec[T] =
    apply(elt0 +: elts.toSeq)

  def tabulate[T <: Data](n: Int)(gen: (Int) => T): Vec[T] = macro VecTransform.tabulate

  def do_tabulate[T <: Data](
    n:   Int
  )(gen: (Int) => T
  )(
    implicit sourceInfo: SourceInfo
  ): Vec[T] =
    apply((0 until n).map(i => gen(i)))

  def tabulate[T <: Data](n: Int, m: Int)(gen: (Int, Int) => T): Vec[Vec[T]] = macro VecTransform.tabulate2D

  def do_tabulate[T <: Data](
    n:   Int,
    m:   Int
  )(gen: (Int, Int) => T
  )(
    implicit sourceInfo: SourceInfo
  ): Vec[Vec[T]] = {
    val elts = Seq.tabulate(n, m)(gen)
    val flatElts = elts.flatten

    require(flatElts.nonEmpty, "Vec hardware values are not allowed to be empty")
    flatElts.foreach(requireIsHardware(_, "vec element"))

    val tpe = cloneSupertype(flatElts, "Vec.tabulate")
    val myVec = Wire(Vec(n, Vec(m, tpe)))
    val op = getConnectOpFromDirectionality(myVec.head.head)
    for {
      (xs1D, ys1D) <- myVec.zip(elts)
      (x, y) <- xs1D.zip(ys1D)
    } {
      op(x, y)
    }
    myVec
  }

  def tabulate[T <: Data](n: Int, m: Int, p: Int)(gen: (Int, Int, Int) => T): Vec[Vec[Vec[T]]] =
    macro VecTransform.tabulate3D

  def do_tabulate[T <: Data](
    n:   Int,
    m:   Int,
    p:   Int
  )(gen: (Int, Int, Int) => T
  )(
    implicit sourceInfo: SourceInfo
  ): Vec[Vec[Vec[T]]] = {
    val elts = Seq.tabulate(n, m, p)(gen)
    val flatElts = elts.flatten.flatten

    require(flatElts.nonEmpty, "Vec hardware values are not allowed to be empty")
    flatElts.foreach(requireIsHardware(_, "vec element"))

    val tpe = cloneSupertype(flatElts, "Vec.tabulate")
    val myVec = Wire(Vec(n, Vec(m, Vec(p, tpe))))
    val op = getConnectOpFromDirectionality(myVec.head.head.head)

    for {
      (xs2D, ys2D) <- myVec.zip(elts)
      (xs1D, ys1D) <- xs2D.zip(ys2D)
      (x, y) <- xs1D.zip(ys1D)
    } {
      op(x, y)
    }

    myVec
  }

  def fill[T <: Data](n: Int)(gen: => T): Vec[T] = macro VecTransform.fill

  def do_fill[T <: Data](n: Int)(gen: => T)(implicit sourceInfo: SourceInfo): Vec[T] =
    if (n == 0) { Wire(Vec(0, gen.cloneTypeFull)) }
    else { apply(Seq.fill(n)(gen)) }

  def fill[T <: Data](n: Int, m: Int)(gen: => T): Vec[Vec[T]] = macro VecTransform.fill2D

  def do_fill[T <: Data](
    n:   Int,
    m:   Int
  )(gen: => T
  )(
    implicit sourceInfo: SourceInfo
  ): Vec[Vec[T]] = {
    do_tabulate(n, m)((_, _) => gen)
  }

  def fill[T <: Data](n: Int, m: Int, p: Int)(gen: => T): Vec[Vec[Vec[T]]] = macro VecTransform.fill3D

  def do_fill[T <: Data](
    n:   Int,
    m:   Int,
    p:   Int
  )(gen: => T
  )(
    implicit sourceInfo: SourceInfo
  ): Vec[Vec[Vec[T]]] = {
    do_tabulate(n, m, p)((_, _, _) => gen)
  }

  def iterate[T <: Data](start: T, len: Int)(f: (T) => T): Vec[T] = macro VecTransform.iterate

  def do_iterate[T <: Data](
    start: T,
    len:   Int
  )(f:     (T) => T
  )(
    implicit sourceInfo: SourceInfo
  ): Vec[T] =
    apply(Seq.iterate(start, len)(f))
}

trait VecLike[T <: Data] extends IndexedSeq[T] with HasId with SourceInfoDoc {

  def apply(p: UInt): T = macro SourceInfoTransform.pArg

  def do_apply(p: UInt)(implicit sourceInfo: SourceInfo): T

  override def hashCode: Int = super[HasId].hashCode
  override def equals(that: Any): Boolean = super[HasId].equals(that)

  def forall(p: T => Bool): Bool = macro SourceInfoTransform.pArg

  def do_forall(p: T => Bool)(implicit sourceInfo: SourceInfo): Bool =
    (this.map(p)).fold(true.B)(_ && _)

  def exists(p: T => Bool): Bool = macro SourceInfoTransform.pArg

  def do_exists(p: T => Bool)(implicit sourceInfo: SourceInfo): Bool =
    (this.map(p)).fold(false.B)(_ || _)

  def contains(x: T)(implicit ev: T <:< UInt): Bool = macro VecTransform.contains

  def do_contains(x: T)(implicit sourceInfo: SourceInfo, ev: T <:< UInt): Bool =
    this.exists(_ === x)

  def count(p: T => Bool): UInt = macro SourceInfoTransform.pArg

  def do_count(p: T => Bool)(implicit sourceInfo: SourceInfo): UInt =
    SeqUtils.count(this.map(p))

  private def indexWhereHelper(p: T => Bool) = this.map(p).zip((0 until length).map(i => i.asUInt))

  def indexWhere(p: T => Bool): UInt = macro SourceInfoTransform.pArg

  def do_indexWhere(p: T => Bool)(implicit sourceInfo: SourceInfo): UInt =
    SeqUtils.priorityMux(indexWhereHelper(p))

  def lastIndexWhere(p: T => Bool): UInt = macro SourceInfoTransform.pArg

  def do_lastIndexWhere(p: T => Bool)(implicit sourceInfo: SourceInfo): UInt =
    SeqUtils.priorityMux(indexWhereHelper(p).reverse)

  def onlyIndexWhere(p: T => Bool): UInt = macro SourceInfoTransform.pArg

  def do_onlyIndexWhere(p: T => Bool)(implicit sourceInfo: SourceInfo): UInt =
    SeqUtils.oneHotMux(indexWhereHelper(p))
}


abstract class Record extends Aggregate {

  protected def _typeNameConParams: Iterable[Any] = Vector.empty

  private[chisel3] def _isOpaqueType: Boolean = this match {
    case maybe: OpaqueType => maybe.opaqueType
    case _ => false
  }

  private def checkClone(clone: Record): Unit = {
    for ((name, field) <- _elements) {
      if (clone._elements(name) eq field) {
        throw new AutoClonetypeException(
          s"The bundle plugin was unable to clone $clone that has field '$name' aliased with base $this." +
            "This likely happened because you tried nesting Data arguments inside of other data structures." +
            " Try wrapping the field(s) in Input(...), Output(...), or Flipped(...) if appropriate." +
            " As a last resort, you can call chisel3.reflect.DataMirror.internal.chiselTypeClone on any nested Data arguments." +
            " See the cookbook entry 'How do I deal with the \"unable to clone\" error?' for more details."
        )
      }
    }
  }

  override def cloneType: this.type = {
    val clone = _cloneTypeImpl.asInstanceOf[this.type]
    checkClone(clone)
    clone
  }

  private def setElementRefs(): Unit = {
    val opaqueType = this._isOpaqueType
    require(
      !opaqueType || (_elements.size == 1 && _elements.head._1 == ""),
      s"Opaque types must have exactly one element with an empty name, not ${_elements.size}: ${elements.keys.mkString(", ")}"
    )
    for ((name, elt) <- _elements) {
      elt.setRef(this, name, opaque = opaqueType)
    }
  }

  private def checkForAndReportDuplicates(): Unit = {
    var duplicates: List[Data] = Nil
    val seen = mutable.HashSet.empty[Data]
    this.elementsIterator.foreach { e =>
      if (seen(e)) {
        duplicates = e :: duplicates
      }
      seen += e
    }
    if (!duplicates.isEmpty) {
      val dupNames = duplicates.toSeq
        .sortBy(_._id)
        .map { duplicate =>
          this._elements.collect { case x if x._2._id == duplicate._id => x }.toSeq
            .sortBy(_._2._id)
            .map(_._1)
            .reverse
            .mkString("(", ",", ")")
        }
        .mkString(",")
      throw new AliasedAggregateFieldException(
        s"${this.className} contains aliased fields named ${dupNames}"
      )
    }
  }

  private[chisel3] var _containsAFlipped: Boolean = false

  override def containsAFlipped: Boolean = _containsAFlipped

  private[chisel3] override def bind(target: Binding, parentDirection: SpecifiedDirection): Unit = {
    this.maybeAddToParentIds(target)
    binding = target

    val resolvedDirection = SpecifiedDirection.fromParent(parentDirection, specifiedDirection)

    checkForAndReportDuplicates()

    for (((_, child), sameChild) <- this.elements.iterator.zip(this.elementsIterator)) {
      if (child != sameChild) {
        throwException(
          s"${this.className} does not return the same objects when calling .elements multiple times. Did you make it a def by mistake?"
        )
      }
      child.bind(ChildBinding(this), resolvedDirection)

      _containsAFlipped |= child.containsAFlipped
    }

    val childDirections = elementsIterator.map(_.direction).toSet - ActualDirection.Empty
    direction = ActualDirection.fromChildren(childDirections, resolvedDirection) match {
      case Some(dir) => dir
      case None =>
        val resolvedDirection = SpecifiedDirection.fromParent(parentDirection, specifiedDirection)
        resolvedDirection match {
          case SpecifiedDirection.Unspecified => ActualDirection.Bidirectional(ActualDirection.Default)
          case SpecifiedDirection.Flip        => ActualDirection.Bidirectional(ActualDirection.Flipped)
          case _                              => ActualDirection.Bidirectional(ActualDirection.Default)
        }
    }
    setElementRefs()

    this match {
      case aliasedRecord: HasTypeAlias => Builder.setRecordAlias(aliasedRecord, resolvedDirection)
      case _ =>
    }
  }

  private[chisel3] def _makeLit(elems: (this.type => (Data, Data))*): this.type = {

    requireIsChiselType(this, "bundle literal constructor model")
    val clone = cloneType
    val cloneFields = getRecursiveFields(clone, "(bundle root)").toMap

    val bundleLitMap = elems.map { fn => fn(clone) }.flatMap {
      case (field, value) =>
        val fieldName = cloneFields.getOrElse(
          field,
          throw new BundleLiteralException(
            s"field $field (with value $value) is not a field," +
              s" ensure the field is specified as a function returning a field on an object of class ${this.getClass}," +
              s" eg '_.a' to select hypothetical bundle field 'a'"
          )
        )
        val valueBinding = value.topBindingOpt match {
          case Some(litBinding: LitBinding) => litBinding
          case _ => throw new BundleLiteralException(s"field $fieldName specified with non-literal value $value")
        }

        field match { // Get the litArg(s) for this field
          case field: Bits =>
            if (field.getClass != value.getClass) { // TODO typeEquivalent is too strict because it checks width
              throw new BundleLiteralException(
                s"Field $fieldName $field specified with non-type-equivalent value $value"
              )
            }
            val litArg = valueBinding match {
              case ElementLitBinding(litArg) => litArg
              case BundleLitBinding(litMap) =>
                litMap.getOrElse(
                  value,
                  throw new BundleLiteralException(s"Field $fieldName specified with unspecified value")
                )
              case VecLitBinding(litMap) =>
                litMap.getOrElse(
                  value,
                  throw new VecLiteralException(s"Vec literal $fieldName specified with out literal values")
                )

            }
            Seq(field -> litArg)

          case field: Record =>
            if (!(field.typeEquivalent(value))) {
              throw new BundleLiteralException(
                s"field $fieldName $field specified with non-type-equivalent value $value"
              )
            }
            val remap = getMatchedFields(value, field).toMap
            value.topBinding.asInstanceOf[BundleLitBinding].litMap.map {
              case (valueField, valueValue) =>
                remap(valueField) -> valueValue
            }

          case vecField: Vec[_] =>
            if (!(vecField.typeEquivalent(value))) {
              throw new BundleLiteralException(
                s"field $fieldName $vecField specified with non-type-equivalent value $value"
              )
            }
            val remap = getMatchedFields(value, vecField).toMap
            value.topBinding.asInstanceOf[VecLitBinding].litMap.map {
              case (valueField, valueValue) =>
                remap(valueField) -> valueValue
            }

          case field: EnumType => {
            if (!(field.typeEquivalent(value))) {
              throw new BundleLiteralException(
                s"field $fieldName $field specified with non-type-equivalent enum value $value"
              )
            }
            val litArg = valueBinding match {
              case ElementLitBinding(litArg) => litArg
              case _ =>
                throw new BundleLiteralException(s"field $fieldName $field could not be matched with $valueBinding")
            }
            Seq(field -> litArg)
          }
          case _ => throw new BundleLiteralException(s"unsupported field $fieldName of type $field")
        }
    }

    val duplicates = bundleLitMap.map(_._1).groupBy(identity).collect { case (x, elts) if elts.size > 1 => x }
    if (!duplicates.isEmpty) {
      val duplicateNames = duplicates.map(cloneFields(_)).mkString(", ")
      throw new BundleLiteralException(s"duplicate fields $duplicateNames in Bundle literal constructor")
    }
    clone.bind(BundleLitBinding(bundleLitMap.toMap))
    clone
  }

  override def toString: String = {
    topBindingOpt match {
      case Some(BundleLitBinding(_)) =>
        val contents = _elements.toList.reverse.map {
          case (name, data) =>
            s"$name=$data"
        }.mkString(", ")
        s"$className($contents)"
      case _ => stringAccessor(s"$className")
    }
  }

  def elements: SeqMap[String, Data]

  private[chisel3] lazy val _elements: VectorMap[String, Data] = {
    val namespace = Option.when(!this._isOpaqueType)(Namespace.empty)
    elements.view.map {
      case (name, field) =>
        if (field.binding.isDefined) {
          throw RebindingException(
            s"Cannot create Record ${this.className}; element ${field} of Record must be a Chisel type, not hardware."
          )
        }
        val sanitizedName = namespace.map(_.name(name, leadingDigitOk = true)).getOrElse(name)
        sanitizedName -> field
    }.to(VectorMap) // VectorMap has O(1) lookup whereas ListMap is O(n)
  }

  def className: String = try {
    this.getClass.getSimpleName
  } catch {
    case e: java.lang.InternalError if e.getMessage == "Malformed class name" => this.getClass.toString
  }

  private[chisel3] final def allElements: Seq[Element] = elementsIterator.flatMap(_.allElements).toIndexedSeq

  override def getElements: Seq[Data] = elementsIterator.toIndexedSeq

  final override private[chisel3] def elementsIterator: Iterator[Data] = _elements.iterator.map(_._2)

  private[chisel3] def toPrintableHelper(elts: Seq[(String, Data)]): Printable = {
    val xs =
      if (elts.isEmpty) List.empty[Printable] // special case because of dropRight below
      else
        elts.flatMap {
          case (name, data) =>
            List(PString(s"$name -> "), data.toPrintable, PString(", "))
        }.dropRight(1) // Remove trailing ", "
    PString(s"$className(") + Printables(xs) + PString(")")
  }

  def toPrintable: Printable = toPrintableHelper(_elements.toList)

  protected def _cloneTypeImpl: Record = {
    throwException(
      s"Internal Error! This should have been implemented by the chisel3-plugin. Please file an issue against chisel3"
    )
  }

  override private[chisel3] lazy val _minId: Long = {
    this.elementsIterator.map(_._minId).foldLeft(this._id)(_ min _)
  }
}

trait IgnoreSeqInBundle {
  this: Bundle =>

  override def ignoreSeq: Boolean = true
}

class AutoClonetypeException(message: String) extends chisel3.ChiselException(message)

package experimental {

  class BundleLiteralException(message: String) extends chisel3.ChiselException(message)
  class VecLiteralException(message: String) extends chisel3.ChiselException(message)

  @deprecated("AutoCloneType is now always enabled, no need to mix it in", "Chisel 3.6")
  trait AutoCloneType { self: Record =>

    override def cloneType: this.type = _cloneTypeImpl.asInstanceOf[this.type]

  }
}

abstract class Bundle extends Record {

  private def mustUsePluginMsg: String =
    "The Chisel compiler plugin is now required for compiling Chisel code. " +
      "Please see https://github.com/chipsalliance/chisel3#build-your-own-chisel-projects."
  assert(_usingPlugin, mustUsePluginMsg)

  override def className: String = try {
    this.getClass.getSimpleName match {
      case name if name.startsWith("$anon$") => "AnonymousBundle" // fallback for anonymous Bundle case
      case ""                                => "AnonymousBundle" // ditto, but on other platforms
      case name                              => name
    }
  } catch {
    case e: java.lang.InternalError if e.getMessage == "Malformed class name" => this.getClass.toString
  }

  final lazy val elements: SeqMap[String, Data] = _processRawElements(_elementsImpl)

  private def _processRawElements(rawElements: Iterable[(String, Any)]): SeqMap[String, Data] = {
    val hardwareFields = rawElements.flatMap {
      case (name, data: Data) =>
        if (data.isSynthesizable) {
          Some(s"$name: $data")
        } else {
          None
        }
      case (name, Some(data: Data)) =>
        if (data.isSynthesizable) {
          Some(s"$name: $data")
        } else {
          None
        }
      case (name, s: scala.collection.Seq[Any]) if s.nonEmpty =>
        s.head match {
          case d: Data =>
            throwException(
              "Public Seq members cannot be used to define Bundle elements " +
                s"(found public Seq member '${name}'). " +
                "Either use a Vec if all elements are of the same type, or MixedVec if the elements " +
                "are of different types. If this Seq member is not intended to construct RTL, mix in the trait " +
                "IgnoreSeqInBundle."
            )
          case _ => // don't care about non-Data Seq
        }
        None

      case _ => None
    }
    if (hardwareFields.nonEmpty) {
      throw ExpectedChiselTypeException(s"Bundle: $this contains hardware fields: " + hardwareFields.mkString(","))
    }
    VectorMap(rawElements.toSeq.flatMap {
      case (name, data: Data) =>
        Some(name -> data)
      case (name, Some(data: Data)) =>
        Some(name -> data)
      case _ => None
    }.sortWith {
      case ((an, a), (bn, b)) => (a._id > b._id) || ((a eq b) && (an > bn))
    }: _*)
  }

  protected def _elementsImpl: Iterable[(String, Any)] = throwException(mustUsePluginMsg)

  def ignoreSeq: Boolean = false

  protected def _usingPlugin: Boolean = false

  override def toPrintable: Printable = toPrintableHelper(_elements.toList.reverse)

}
